#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 剑指 Offer 36. 二叉搜索树与双向链表.py
@time: 2022/3/3 14:15
@desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
> 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

1. dfs, Ot(N), Os(N)
'''
"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""


class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            # 中序遍历

            # 左子树
            dfs(cur.left)

            # 处理当前结点
            # 若pre为空，则说明当前结点为空
            if not self.pre:
                self.head = cur
            # 若不为空，则重新建立连接关系
            else:
                self.pre.right = cur
                cur.left = self.pre

            self.pre = cur
            # 右子树
            dfs(cur.right)

        if not root: return
        self.pre, self.head = None, None
        dfs(root)
        # 此时pre已经到了叶子节点
        self.pre.right, self.head.left = self.head, self.pre
        return self.head